#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@Author  :   JingV
@Version :   1.0
@Contact :   None
@License :   None
@Desc    :   None
'''


class Solution(object):
    def exist(self, board, word):
        # 处理边界情况
        if len(word) == 0 or not board or not board[0]:
            return False

        from collections import deque
        directs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        len_word, board_row, board_column = len(word), len(board), len(board[0])

        queue = deque()
        # 任意一个元素都有可能是入口, 将其入队
        for row in range(board_row):
            for column in range(board_column):
                queue.append(((row, column), 0, []))

        while queue:
            index_board, index_word, visited_index = queue.popleft()
            # 如果board中的字符与word中的字符相同,则进行下一次比较, 否则不进行比较
            if board[index_board[0]][index_board[1]] == word[index_word]:
                # 如当前是word中的最后一个字符, 则说明前面的匹配成功
                if index_word == len_word - 1:
                    return True
                # 检查相邻的元素
                for direct in directs:
                    # 获取新的下标
                    new_row_index, new_column_index = index_board[0] + direct[0], index_board[1] + direct[1]
                    # 如果当前索引符合规范(没有越界, 没有被访问过)
                    if 0 <= new_row_index < board_row and 0 <= new_column_index < board_column and (new_row_index, new_column_index) not in visited_index:
                        queue.append(((new_row_index, new_column_index), index_word + 1, visited_index + [index_board])) 
        return False


def main():
    solution = Solution()
    tests = [
        (
            [["a"]], "a",
        ),
        (
            [["a", "b"]], "ab",
        ),
        (
            [
                ['A', 'B', 'C', 'E'],
                ['S', 'F', 'C', 'S'],
                ['A', 'D', 'E', 'E'],
            ],
            "ABCCED",
        ),
        (
            [
                ['A', 'B', 'C', 'E'],
                ['S', 'F', 'C', 'S'],
                ['A', 'D', 'E', 'E'],
            ],
            "SEE",
        ),
        (
            [
                ['A', 'B', 'C', 'E'],
                ['S', 'F', 'C', 'S'],
                ['A', 'D', 'E', 'E'],
            ],
            "AEE",
        ),
    ]
    for board, word in tests:
        print(solution.exist(board, word))


if __name__ == "__main__":
    main()
